# 树是一种数据结构 比如:目录结构
# 树是一种可以递归定义的数据结构
# 树是指由N(N>=0)个有限节点组成的具有层次关系的集合，是一种简单的非线性结构。当N=0时,称为空树。
# 树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：
# 1.数的根节点没有前驱节点，除根节点以外的所有节点有且只有一个前驱节点。
# 2.树中可以有零个或多个后继节点。
# 树的基本概念
# 根节点：在树结构中，只有一个节点没有前件，该节点称为根节点
# 父节点：在树结构中，每个节点只有一个前件，这个节点就是该节点的父节点
# 子节点：在树结构中，每个节点可以有多个后件，这些后件就是该节点的子节点
# 叶子节点：在树结构中，没有后件的节点称为叶子节点
# 度：树中一个节点的子节点的个数称为该节点的度，树中节点的最大度数称为树的度(最大的子节点数)
# 树的深度：在树结构中，根节点所在的层次为1，其他节点所在的层次为其父节点所在的层次+1，最大层次称为树的深度
# 子树：在树结构中，以某一个节点的一个子节点为根节点构成的树，称为该节点的子树
# 树的性质
# 总分支数=1xN1+2xN2+...+mxNm(度为m的节点引出的m条分支)
# 总节点数=N0+N1+..Nm
# 树中的节点树等于所有节点度数加1
# 度为m的树中第i层上至多有m^(i-1)个节点
# 二叉树的基本概念
# 二叉树是一种树型结构，其特点是每个节点至多只有2棵子树(即二叉树中不存在度>2的节点)。并且树的子树有左右之分，次序不能颠倒
# 当n=0时，为空二叉树
# 当n>=1时，二叉树由一个根节点和两个互不相交的被称为左子树和右子树组成，左右子树分别又是一棵二叉树
# 满二叉树：高度为h,含有2^(h-1)个节点的二叉树称为满二叉树
# 完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树一一对应，称为完全二叉树
# 二叉树的性质
# 1.非空二叉树上的叶子节点数等于度为2的节点数加1，即total = N2+1
# 2.非空二叉树上第K层至多有2^(k-1)个节点(k>=1)
# 3.高度为H的二叉树至多有2*H-1个节点(H>=1)
# 4.具有N(N>0)个节点的完全二叉树的高度为向上取整(log2(N+1))或向下取整(log2N+1)
# 二叉树的存储结构
# 二叉树的存储结构分为顺序存储和链式存储
# 1.顺序存储：二叉树的顺序存储就是用一组连续的存储单元存放二叉树中的节点元素，一般按照自上而下，自左向右的顺序存储。
# 2.链式存储：二叉树的链式存储结构是用一个链表来存储一棵二叉树，二叉树中的每个节点用链表的一个链节点来存储[左指针域,数据域,右指针域]
# 二叉树的遍历
# 所谓二叉树的遍历，是指按某条搜索路径访问树中的每个节点，使得每个节点均被访问一次，并且仅被访问一次，常见的三种遍历方法分别是，前序遍历，中序遍历，后序遍历，层次遍历
# 1.前序遍历(DLR):首先访问根节点，其次遍历左子树，最后遍历右子树。
# 2.中序遍历(LDR):先遍历左子树，根节点，右子树
# 3.后序遍历(RDL):先遍历右子树，左子树，根节点
# 4.层次遍历：先遍历根节点
